package com.dy.分类.递归回溯分治.N皇后;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 * <p>
 * <p>
 * <p>
 * 上图为 8 皇后问题的一种解法。
 * <p>
 * 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
 * <p>
 * 每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 */
public class Solution {
    static final int dx[] = {-1, 1, 0, 0, 1, -1, 1, -1};//方向数组
    static final int dy[] = {0, 0, 1, -1, 1, -1, -1, 1};

    public List<List<String>> solveNQueens(int n) {
        //初始化棋盘都为".", 初始化mask 都可以放
        List<List<String>> res = new LinkedList<>();
        boolean[][] mask = new boolean[n][n];
        char location[][] = new char[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                mask[i][j] = true;
                location[i][j] = '.';
            }
        }

        huisu(0, n, mask, location, res);
        return res;


    }

    void huisu(int k, int n, boolean[][] mask, char location[][], List<List<String>> res) {
        //k表示正在放第k行皇后，已经放置了0～k-1行的皇后，已经放置了k个皇后,记录
        if (k == n) {
            List<String> s = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                s.add(i, new String(location[i]));

            }
            res.add(s);
            return;
        }

        //放置到第i列
        for(int j=0;j<n;j++){
            if(mask[k][j]==true){
                boolean maskbkp[][] = new boolean[n][n];
                copy(mask,maskbkp);
                //设置标记
                putDownTheQueue(k,j,mask);
                //并复制一个mask数组,用于备份

                location[k][j]='Q';

                //放置下一行
                huisu(k+1,n,mask, location, res);
                //回溯
                copy(maskbkp,mask);
                location[k][j]='.';
            }
        }

    }

    //当在x，y放置皇后后，将八个方向的mark都置为1
    void putDownTheQueue(int x, int y, boolean[][] mark) {
        mark[x][y] = false;
        for (int i = 1; i < mark.length; i++) { //延伸多远，从1到N-1;
            for (int j = 0; j < 8; j++) { //8个方向
                int newX = x + i * dx[j];
                int newY = y + i * dy[j];
                if (newX >= 0 && newX < mark.length && newY >= 0 && newY < mark.length) {
                    mark[newX][newY] = false;
                }
            }
        }
    }
    void copy(boolean[][]nums1,boolean[][]nums2){
        for(int i=0;i<nums1.length;i++){
            for(int j=0;j<nums1.length;j++){
                nums2[i][j]=nums1[i][j];
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solveNQueens(4);
    }
}
